package main

//#link: https://leetcode-cn.com/problems/implement-trie-prefix-tree/
func main() {

}

type Trie struct {
	//trie[] 来存储所有的单词字符
	tire [][26]int
	//count数组记录某个格子被「被标记为结尾的次数」
	count []int
	//记录我们到底用了多少个格子
	index int
}

var (
	N = 100009
)

/** Initialize your data structure here. */
func Constructor() Trie {
	return Trie{
		tire:  make([][26]int, N),
		count: make([]int, N),
		index: 0,
	}
}

/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
	p := 0
	for i := 0; i < len(word); i++ {
		u := word[i] - 'a'
		if this.tire[p][u] == 0 {
			this.index++
			this.tire[p][u] = this.index
		}
		p = this.tire[p][u]
	}
	this.count[p]++
}

/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
	p := 0
	for i := 0; i < len(word); i++ {
		u := word[i] - 'a'
		//说明数组中还未存在此字符
		if this.tire[p][u] == 0 {
			return false
		}
		p = this.tire[p][u]
	}
	return this.count[p] != 0
}

/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
	p := 0
	for i := 0; i < len(prefix); i++ {
		u := prefix[i] - 'a'
		//说明数组中还未存在此字符
		if this.tire[p][u] == 0 {
			return false
		}
		p = this.tire[p][u]
	}
	return true
}

/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */
